/**
 * @(#)LC845数组中最长的山脉.java, 9月 28, 2021.
 * <p>
 * Copyright 2021 fenbi.com. All rights reserved.
 * FENBI.COM PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
 */
package com.wxweven.algorithm.array;

/**
 * @author wxweven
 */
public class LC845数组中最长的山脉 {

    /*
     *我们把数组 A 中符合下列属性的任意连续子数组 B 称为 “山脉”：
     *
     * B.length >= 3
     * 存在 0 < i < B.length - 1 使得 B[0] < B[1] < ... B[i-1] < B[i] > B[i+1] > ... > B[B.length - 1]
     * （注意：B 可以是 A 的任意子数组，包括整个数组 A。）
     *
     * 给出一个整数数组 A，返回最长 “山脉” 的长度。
     *
     * 如果不含有 “山脉” 则返回 0。
     *
     *  
     *
     * 示例 1：
     *
     * 输入：[2,1,4,7,3,2,5]
     * 输出：5
     * 解释：最长的 “山脉” 是 [1,4,7,3,2]，长度为 5。
     * 示例 2：
     *
     * 输入：[2,2,2]
     * 输出：0
     * 解释：不含 “山脉”。
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/longest-mountain-in-array
     */

    public int longestMountain(int[] arr) {
        if (arr == null || arr.length < 3) {
            return 0;
        }

        int start = -1;
        int res = 0;

        int len = arr.length;
        for (int i = 1; i < len; i++) {
            // 确定起点
            if (arr[i - 1] < arr[i]) {
                // 说明当前处于上升阶段，需要确定山脉的起点
                // 什么时候是山脉的起点呢，如果前前一个元素，大于等于前一个元素，
                // 那么说明前一个元素是山脉的起点
                // 如图： \_/
                if (i == 1 || arr[i - 2] >= arr[i - 1]) {
                    start = i - 1;
                }
            } else if (arr[i - 1] > arr[i]) {
                // 说明开始下降了，可以动态更新山脉的长度了
                // 前提是山脉有起点，防止数组一上来就是下降的
                if (start != -1) {
                    res = Math.max(res, i - start + 1);
                }

            } else {
                // 当前元素和前一个相等，start需要重置了
                start = -1;
            }
        }

        return res;
    }
}